アルゴリズム解析・設計 期末課題
テスト
形式など
13日まで
40分
選択式
計算あり
調べて良い
疑問点を潰しておく
対策
範囲
Tree 木構造まで
graph入らない
データ構造 Data Structure 3h+1.5h
配列 Array
連結リスト Linked list 連想配列 辞書 object
Stack スタック
Queue キュー
Tree 木構造 1.5h
アルゴリズム Algorithms
search 探索 2h
線形探索 Linear search
二分探索 Binary search
ハッシュ探索 hash search
Sorting ソート 整列 4h
Bubble Sort バブルソート
Selection Sort 選択ソート
Shellsort シェルソート
Quicksort クイックソート
挿入ソート Insertion sort
Merge Sort マージソート
Heap Sort ヒープソート
計数ソート counting sort
基数ソート radix sort
Bucket Sort バケットソート
その他 3h
Recursion 再帰
自然数
最大公約数 Greatest common divisor
ユークリッドの互除法
トップダウン解析 top-down analysis
ボトムアップ解析 bottom-up analysis
フィボナッチ数列
メモ化 memorization
ハノイの塔
n-queeens
分割統治法
レポート
Quicksort クイックソートの最悪時の改善 4h
10講
クイックソート(quick sort)は平均時間計算量が 𝑂$ 𝑛 log_2 𝑛 の高速な整 列アルゴリズムだが，アルゴリズムの設定および処理するデータ列の構成 次第で時間計算量が $ O(n^2) になる.
クイックソートの性能が最悪になるのはどのような場合かを説明せよ.
さらに，そのような最悪ケースを回避するための有効な対策を挙げよ
回答
最悪の場合
各レベルで１つの要素とそれ以外という分割が行われる場合
つまり？
データ列の並び方が悪い時
悪い時?
枢軸 pivotによる分割
回避対策
枢軸 pivotをデータ列の最初と中央と最後の3要素の中央値を用いる
データ列が偶数個の場合
中央が２つあるので、2つの要素の平均値を使う
乱数を用いて乱数選択
トリボナッチ数 Tribonacci numberの実装 4h
1 トリボナッチ数列の第 n 項の値を求める再帰関数を設計せよ.
2 1で設計した再帰関数をメモ化によって効率化せよ.